/*
day256
2020.5.10
*/
#include<map>
#include<vector>
#include<cstdlib> 
using namespace std;

struct TreeNode {
    int val;
	TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
		map<int,int> m;
		int cur_sum=0;
		int res=0;
		
		help(root,m,cur_sum,sum,res);
		
		return res;
    }
    
    void help(TreeNode *root,map<int,int> &m,int cur_sum,int sum,int &res)
    {
    	if(!root)
    	{
    		return ;
		}
		
		cur_sum+=root->val;
		
		if(cur_sum==sum)
		{
			res++;
		}
		
		res+=m[cur_sum-sum];
		
		m[cur_sum]++;
		help(root->left,m,cur_sum,sum,res);
		help(root->right,m,cur_sum,sum,res);
		m[cur_sum]--;
	}
};

int main()
{
	return 0;
}
